package com.xiaofu.sort.insertion;

import com.xiaofu.sort.Sort;

/**
 * @author: xiaofu
 * @DESCRIPTION: a technology seeker
 * @date: 2021-08-05 0:40
 */
public class InsertionSort extends Sort {
    @Override
    protected void sort() {
        sort3();
    }

    protected void sort1(){
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            while (cur > 0 && cmp(cur, cur - 1) < 0) {
                swap(cur, cur - 1);
                cur--;
            }
        }
    }

    protected void sort2() {
        for (int begin = 1; begin < array.length; begin++) {
            int cur = begin;
            Integer bak = array[cur];
            while (cur > 0 && cmp(cur, cur - 1) < 0) {
                array[cur] = array[cur - 1];
                cur--;
            }
            array[cur] = bak;
        }
    }

    protected void sort3() {
        for (int begin = 1; begin < array.length; begin++) {
            Integer v = array[begin];
            int search = search(begin);
            for (int i = begin ; i > search; i--) {
                array[i] = array[i-1];
            }
            array[search] = v;
        }
    }

    /**
     * 利用二分查找找到index位置元素的待插入位置
     * 已经排好序的数组的区间范围是[0,index)
     *
     * @param index
     * @return
     */
    private int search(int index) {
        int begin = 0;
        int end = index;
        while (begin < end) {
            int mid = (begin + end) >> 1;
            if (cmp(index,mid) < 0) {
                end = mid;
            } else {
                begin = mid + 1;
            }
        }
        return begin;
    }
}
